package leetcode.code0417;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

//  错了，深度优先遍历不太对啊
public class Solution2 implements IDebug {

	int m, n;

	int[] d = new int[] { 0, 1, 0, -1, 1, 0, -1, 0 };

	public List<List<Integer>> pacificAtlantic(int[][] heights) {
		m = heights.length;
		n = heights[0].length;
		Boolean[][] pacific = new Boolean[m][n];
		Boolean[][] atlantic = new Boolean[m][n];
		boolean[][] pb = new boolean[m][n];
		boolean[][] ab = new boolean[m][n];
		List<List<Integer>> ans = new ArrayList<>();
		for (int i = 0; i < m; i++) {
			HelpDebug.print(pacific);
			for (int j = 0; j < n; j++) {
				if (this.f(heights, i, j, pacific, pb, atlantic, ab)) {
					ans.add(Arrays.asList(i, j));
				}
			}
		}
//		H.printObject(pacific);
//		H.printObject(atlantic);
		return ans;
	}

	private boolean f(int[][] heights, int i, int j, Boolean[][] pacific, boolean[][] pb, Boolean[][] atlantic,
			boolean[][] ab) {
		return this.pacific(heights, i, j, pacific, pb) && this.atlantic(heights, i, j, atlantic, ab);
	}

	// 能不能去太平洋
	private boolean pacific(int[][] heights, int i, int j, Boolean[][] pacific, boolean[][] b) {
		if (i < 0 || i >= m || j < 0 || j >= n || b[i][j]) {
			return false;
		}
		if (i == 0 || j == 0) {
			pacific[i][j] = true;
			return true;
		}
//		if (pacific[i][j] != null) {
//			return pacific[i][j];
//		}
		int h = heights[i][j];
		b[i][j] = true;
		for (int k = 0; k < 8; k += 2) {
			int nexti = i + d[k], nextj = j + d[k + 1];
			if (this.pacific(heights, nexti, nextj, pacific, b) && h >= heights[nexti][nextj]) {
				pacific[i][j] = true;
				return true;
			}
		}
		pacific[i][j] = false;
		return false;
	}

	// 能不能去大西洋
	private boolean atlantic(int[][] heights, int i, int j, Boolean[][] atlantic, boolean[][] b) {
		if (i < 0 || i >= m || j < 0 || j >= n || b[i][j]) {
			return false;
		}
		if (i == m - 1 || j == n - 1) {
			atlantic[i][j] = true;
			return true;
		}
		if (atlantic[i][j] != null) {
			return atlantic[i][j];
		}
		int h = heights[i][j];
		b[i][j] = true;
		for (int k = 0; k < 8; k += 2) {
			int nexti = i + d[k], nextj = j + d[k + 1];
			if (this.atlantic(heights, nexti, nextj, atlantic, b) && h >= heights[nexti][nextj]) {
				atlantic[i][j] = true;
				return true;
			}
		}
		atlantic[i][j] = false;
		return false;
	}

	@Override
	public void debug1() {
		List<List<Integer>> e = HelpDebug.str2intlist1("[[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]");
		HelpDebug.compare(e,
				this.pacificAtlantic(HelpDebug.str2array1("[[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]")));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
